package jianzhi; /**
 * description:
 * author:张腾
 * date:2021-06-30
 */

import niuke.TreeNode;

import java.util.LinkedList;

/**
 * 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
 *
 * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 */
public class jianzhi37 {
    public class Codec {
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root==null) return "[]";
            StringBuffer sb = new StringBuffer("[");
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                TreeNode cur = queue.poll();
                if (cur!=null){
                    sb.append(cur.val+",");
                    queue.add(cur.left);
                    queue.add(cur.right);
                }else sb.append("null,");
            }
            sb.deleteCharAt(sb.length()-1);
            sb.append("]");
            return sb.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.equals("[]")) return null;
            String[] vals = data.substring(1, data.length() - 1).split(",");
            LinkedList<TreeNode> queue = new LinkedList<>();
            TreeNode root = new TreeNode(Integer.valueOf(vals[0]));
            queue.add(root);
            int i = 1;
            while (!queue.isEmpty()){
                TreeNode cur = queue.poll();
                if (!vals[i].equals("null")){
                    cur.left = new TreeNode(Integer.valueOf(vals[i]));
                    queue.add(cur.left);
                }
                i++;
                if (!vals[i].equals("null")){
                    cur.right = new TreeNode(Integer.valueOf(vals[i]));
                    queue.add(cur.right);
                }
                i++;
            }
            return root;
        }
    }
}
